<?xml version="1.0" encoding="ascii"?>
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN"
          "DTD/xhtml1-transitional.dtd">
<html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en" lang="en">
<head>
  <title>equivalence</title>
  <link rel="stylesheet" href="epydoc.css" type="text/css" />
  <script type="text/javascript" src="epydoc.js"></script>
</head>

<body bgcolor="white" text="black" link="blue" vlink="#204080"
      alink="#204080">
<!-- ==================== NAVIGATION BAR ==================== -->
<table class="navbar" border="0" width="100%" cellpadding="0"
       bgcolor="#a0c0ff" cellspacing="0">
  <tr valign="middle">
  <!-- Home link -->
      <th bgcolor="#70b0f0" class="navbar-select"
          >&nbsp;&nbsp;&nbsp;Home&nbsp;&nbsp;&nbsp;</th>

  <!-- Tree link -->
      <th>&nbsp;&nbsp;&nbsp;<a
        href="module-tree.html">Trees</a>&nbsp;&nbsp;&nbsp;</th>

  <!-- Index link -->
      <th>&nbsp;&nbsp;&nbsp;<a
        href="identifier-index.html">Indices</a>&nbsp;&nbsp;&nbsp;</th>

  <!-- Help link -->
      <th>&nbsp;&nbsp;&nbsp;<a
        href="help.html">Help</a>&nbsp;&nbsp;&nbsp;</th>

  <!-- Project homepage -->
      <th class="navbar" align="right" width="100%">
        <table border="0" cellpadding="0" cellspacing="0">
          <tr><th class="navbar" align="center"
            >equivalence</th>
          </tr></table></th>
  </tr>
</table>
<table width="100%" cellpadding="0" cellspacing="0">
  <tr valign="top">
    <td width="100%">
      <span class="breadcrumbs">
        Module&nbsp;equivalence
      </span>
    </td>
    <td>
      <table cellpadding="0" cellspacing="0">
        <!-- hide/show private -->
        <tr><td align="right"><span class="options">[<a href="javascript:void(0);" class="privatelink"
    onclick="toggle_private();">hide&nbsp;private</a>]</span></td></tr>
        <tr><td align="right"><span class="options"
            >[<a href="frames.html" target="_top">frames</a
            >]&nbsp;|&nbsp;<a href="equivalence-pysrc.html"
            target="_top">no&nbsp;frames</a>]</span></td></tr>
      </table>
    </td>
  </tr>
</table>
<h1 class="epydoc">Source Code for <a href="equivalence-module.html">Module equivalence</a></h1>
<pre class="py-src">
<a name="L1"></a><tt class="py-lineno">  1</tt>  <tt class="py-line"><tt class="py-docstring">'''A pure Python implementation of equivalence relations.'''</tt> </tt>
<a name="L2"></a><tt class="py-lineno">  2</tt>  <tt class="py-line"> </tt>
<a name="L3"></a><tt class="py-lineno">  3</tt>  <tt class="py-line"><tt class="py-name">__all__</tt> <tt class="py-op">=</tt> <tt class="py-op">[</tt><tt class="py-string">'equivalence'</tt><tt class="py-op">,</tt> <tt class="py-string">'Equivalence'</tt><tt class="py-op">]</tt> </tt>
<a name="L4"></a><tt class="py-lineno">  4</tt>  <tt class="py-line"><tt class="py-name">__docformat__</tt> <tt class="py-op">=</tt> <tt class="py-string">"restructuredtext en"</tt> </tt>
<a name="L5"></a><tt class="py-lineno">  5</tt>  <tt class="py-line"> </tt>
<a name="L6"></a><tt class="py-lineno">  6</tt>  <tt class="py-line"><tt class="py-keyword">from</tt> <tt class="py-name">itertools</tt> <tt class="py-keyword">import</tt> <tt class="py-name">izip</tt> </tt>
<a name="L7"></a><tt class="py-lineno">  7</tt>  <tt class="py-line"><tt class="py-keyword">from</tt> <tt class="py-name">collections</tt> <tt class="py-keyword">import</tt> <tt class="py-name">defaultdict</tt> </tt>
<a name="L8"></a><tt class="py-lineno">  8</tt>  <tt class="py-line"> </tt>
<a name="L9"></a><tt class="py-lineno">  9</tt>  <tt class="py-line"> </tt>
<a name="equivalence"></a><div id="equivalence-def"><a name="L10"></a><tt class="py-lineno"> 10</tt> <a class="py-toggle" href="#" id="equivalence-toggle" onclick="return toggle('equivalence');">-</a><tt class="py-line"><tt class="py-keyword">def</tt> <a class="py-def-name" href="equivalence-module.html#equivalence">equivalence</a><tt class="py-op">(</tt><tt class="py-param">key</tt><tt class="py-op">=</tt><tt class="py-name">None</tt><tt class="py-op">,</tt> <tt class="py-param">bidirectional</tt><tt class="py-op">=</tt><tt class="py-name">False</tt><tt class="py-op">)</tt><tt class="py-op">:</tt> </tt>
</div><div id="equivalence-collapsed" style="display:none;" pad="+++" indent="++++"></div><div id="equivalence-expanded"><a name="L11"></a><tt class="py-lineno"> 11</tt>  <tt class="py-line">    <tt class="py-docstring">'''Factory function for creating an appropriate `Equivalence` instance.</tt> </tt>
<a name="L12"></a><tt class="py-lineno"> 12</tt>  <tt class="py-line"><tt class="py-docstring"></tt> </tt>
<a name="L13"></a><tt class="py-lineno"> 13</tt>  <tt class="py-line"><tt class="py-docstring">    To facilitate future API changes, all arguments to this function should be</tt> </tt>
<a name="L14"></a><tt class="py-lineno"> 14</tt>  <tt class="py-line"><tt class="py-docstring">    passed as keywords.</tt> </tt>
<a name="L15"></a><tt class="py-lineno"> 15</tt>  <tt class="py-line"><tt class="py-docstring"></tt> </tt>
<a name="L16"></a><tt class="py-lineno"> 16</tt>  <tt class="py-line"><tt class="py-docstring">    :type key: None or callable ``key(x)``</tt> </tt>
<a name="L17"></a><tt class="py-lineno"> 17</tt>  <tt class="py-line"><tt class="py-docstring">    :param key: The key function to be used for determining implicit equivalence,</tt> </tt>
<a name="L18"></a><tt class="py-lineno"> 18</tt>  <tt class="py-line"><tt class="py-docstring">        or None if there is not a key function.</tt> </tt>
<a name="L19"></a><tt class="py-lineno"> 19</tt>  <tt class="py-line"><tt class="py-docstring">    :type bidirectional: bool</tt> </tt>
<a name="L20"></a><tt class="py-lineno"> 20</tt>  <tt class="py-line"><tt class="py-docstring">    :param bidirectional: If true, the `Equivalence.partition` method takes</tt> </tt>
<a name="L21"></a><tt class="py-lineno"> 21</tt>  <tt class="py-line"><tt class="py-docstring">        linear time to the size of the given object's equivalence set, as opposed</tt> </tt>
<a name="L22"></a><tt class="py-lineno"> 22</tt>  <tt class="py-line"><tt class="py-docstring">        to the size of the whole equivalence relation if `bidirectional` is false.</tt> </tt>
<a name="L23"></a><tt class="py-lineno"> 23</tt>  <tt class="py-line"><tt class="py-docstring">        The downside is increased memory overhead and extra constant factor cost</tt> </tt>
<a name="L24"></a><tt class="py-lineno"> 24</tt>  <tt class="py-line"><tt class="py-docstring">        for the rest methods.</tt> </tt>
<a name="L25"></a><tt class="py-lineno"> 25</tt>  <tt class="py-line"><tt class="py-docstring">    :rtype: `Equivalence`</tt> </tt>
<a name="L26"></a><tt class="py-lineno"> 26</tt>  <tt class="py-line"><tt class="py-docstring">    '''</tt> </tt>
<a name="L27"></a><tt class="py-lineno"> 27</tt>  <tt class="py-line">    <tt class="py-keyword">if</tt> <tt class="py-name">key</tt> <tt class="py-keyword">is</tt> <tt class="py-name">None</tt><tt class="py-op">:</tt> </tt>
<a name="L28"></a><tt class="py-lineno"> 28</tt>  <tt class="py-line">        <tt class="py-keyword">return</tt> <tt class="py-op">(</tt><tt class="py-name">bidirectional</tt> <tt class="py-keyword">and</tt> <tt id="link-0" class="py-name" targets="Class equivalence.BidirectionalEquivalence=equivalence.BidirectionalEquivalence-class.html"><a title="equivalence.BidirectionalEquivalence" class="py-name" href="#" onclick="return doclink('link-0', 'BidirectionalEquivalence', 'link-0');">BidirectionalEquivalence</a></tt> <tt class="py-keyword">or</tt> <tt id="link-1" class="py-name" targets="Class equivalence.Equivalence=equivalence.Equivalence-class.html"><a title="equivalence.Equivalence" class="py-name" href="#" onclick="return doclink('link-1', 'Equivalence', 'link-1');">Equivalence</a></tt><tt class="py-op">)</tt><tt class="py-op">(</tt><tt class="py-op">)</tt> </tt>
<a name="L29"></a><tt class="py-lineno"> 29</tt>  <tt class="py-line">    <tt class="py-keyword">else</tt><tt class="py-op">:</tt> </tt>
<a name="L30"></a><tt class="py-lineno"> 30</tt>  <tt class="py-line">        <tt class="py-keyword">return</tt> <tt class="py-op">(</tt><tt class="py-name">bidirectional</tt> <tt class="py-keyword">and</tt> <tt id="link-2" class="py-name" targets="Class equivalence.KeyBidirectionalEquivalence=equivalence.KeyBidirectionalEquivalence-class.html"><a title="equivalence.KeyBidirectionalEquivalence" class="py-name" href="#" onclick="return doclink('link-2', 'KeyBidirectionalEquivalence', 'link-2');">KeyBidirectionalEquivalence</a></tt> <tt class="py-keyword">or</tt> <tt id="link-3" class="py-name" targets="Class equivalence.KeyEquivalence=equivalence.KeyEquivalence-class.html"><a title="equivalence.KeyEquivalence" class="py-name" href="#" onclick="return doclink('link-3', 'KeyEquivalence', 'link-3');">KeyEquivalence</a></tt><tt class="py-op">)</tt><tt class="py-op">(</tt><tt class="py-name">key</tt><tt class="py-op">)</tt> </tt>
</div><a name="L31"></a><tt class="py-lineno"> 31</tt>  <tt class="py-line"> </tt>
<a name="L32"></a><tt class="py-lineno"> 32</tt>  <tt class="py-line"> </tt>
<a name="Equivalence"></a><div id="Equivalence-def"><a name="L33"></a><tt class="py-lineno"> 33</tt> <a class="py-toggle" href="#" id="Equivalence-toggle" onclick="return toggle('Equivalence');">-</a><tt class="py-line"><tt class="py-keyword">class</tt> <a class="py-def-name" href="equivalence.Equivalence-class.html">Equivalence</a><tt class="py-op">(</tt><tt class="py-base-class">object</tt><tt class="py-op">)</tt><tt class="py-op">:</tt> </tt>
</div><div id="Equivalence-collapsed" style="display:none;" pad="+++" indent="++++"></div><div id="Equivalence-expanded"><a name="L34"></a><tt class="py-lineno"> 34</tt>  <tt class="py-line">    <tt class="py-docstring">'''Basic equivalence relation.</tt> </tt>
<a name="L35"></a><tt class="py-lineno"> 35</tt>  <tt class="py-line"><tt class="py-docstring"></tt> </tt>
<a name="L36"></a><tt class="py-lineno"> 36</tt>  <tt class="py-line"><tt class="py-docstring">    An `Equivalence` instance maintains a partition of objects into sets so that</tt> </tt>
<a name="L37"></a><tt class="py-lineno"> 37</tt>  <tt class="py-line"><tt class="py-docstring">    the equivalence properties (reflexivity, symmetry, transitivity) are preserved.</tt> </tt>
<a name="L38"></a><tt class="py-lineno"> 38</tt>  <tt class="py-line"><tt class="py-docstring">    Two objects ``a`` and ``b`` are considered equivalent after `merge(a,b)`.</tt> </tt>
<a name="L39"></a><tt class="py-lineno"> 39</tt>  <tt class="py-line"><tt class="py-docstring"></tt> </tt>
<a name="L40"></a><tt class="py-lineno"> 40</tt>  <tt class="py-line"><tt class="py-docstring">    This implementation uses a `disjoint-set forests`_ data structure with</tt> </tt>
<a name="L41"></a><tt class="py-lineno"> 41</tt>  <tt class="py-line"><tt class="py-docstring">    *union by rank* and *path compression* so most operations have almost</tt> </tt>
<a name="L42"></a><tt class="py-lineno"> 42</tt>  <tt class="py-line"><tt class="py-docstring">    constant amortized time. The main exception is `partition`, which is linear</tt> </tt>
<a name="L43"></a><tt class="py-lineno"> 43</tt>  <tt class="py-line"><tt class="py-docstring">    to the size of the **whole equivalence** and should therefore be avoided for</tt> </tt>
<a name="L44"></a><tt class="py-lineno"> 44</tt>  <tt class="py-line"><tt class="py-docstring">    large relations.</tt> </tt>
<a name="L45"></a><tt class="py-lineno"> 45</tt>  <tt class="py-line"><tt class="py-docstring"></tt> </tt>
<a name="L46"></a><tt class="py-lineno"> 46</tt>  <tt class="py-line"><tt class="py-docstring">    .. _`disjoint-set forests`: http://en.wikipedia.org/wiki/Disjoint-set_data_structure</tt> </tt>
<a name="L47"></a><tt class="py-lineno"> 47</tt>  <tt class="py-line"><tt class="py-docstring">    '''</tt> </tt>
<a name="L48"></a><tt class="py-lineno"> 48</tt>  <tt class="py-line"> </tt>
<a name="Equivalence.__init__"></a><div id="Equivalence.__init__-def"><a name="L49"></a><tt class="py-lineno"> 49</tt> <a class="py-toggle" href="#" id="Equivalence.__init__-toggle" onclick="return toggle('Equivalence.__init__');">-</a><tt class="py-line">    <tt class="py-keyword">def</tt> <a class="py-def-name" href="equivalence.Equivalence-class.html#__init__">__init__</a><tt class="py-op">(</tt><tt class="py-param">self</tt><tt class="py-op">)</tt><tt class="py-op">:</tt> </tt>
</div><div id="Equivalence.__init__-collapsed" style="display:none;" pad="+++" indent="++++++++"></div><div id="Equivalence.__init__-expanded"><a name="L50"></a><tt class="py-lineno"> 50</tt>  <tt class="py-line">        <tt class="py-docstring">'''Intialize this equivalence.'''</tt> </tt>
<a name="L51"></a><tt class="py-lineno"> 51</tt>  <tt class="py-line">        <tt class="py-comment"># maps an object to its parent in the disjoint-set forest</tt> </tt>
<a name="L52"></a><tt class="py-lineno"> 52</tt>  <tt class="py-line"><tt class="py-comment"></tt>        <tt class="py-name">self</tt><tt class="py-op">.</tt><tt class="py-name">_child2parent</tt> <tt class="py-op">=</tt> <tt class="py-op">{</tt><tt class="py-op">}</tt> </tt>
<a name="L53"></a><tt class="py-lineno"> 53</tt>  <tt class="py-line">        <tt class="py-comment"># maps an object to its rank in the disjoint-set</tt> </tt>
<a name="L54"></a><tt class="py-lineno"> 54</tt>  <tt class="py-line"><tt class="py-comment"></tt>        <tt class="py-name">self</tt><tt class="py-op">.</tt><tt class="py-name">_rank</tt> <tt class="py-op">=</tt> <tt class="py-op">{</tt><tt class="py-op">}</tt> </tt>
</div><a name="L55"></a><tt class="py-lineno"> 55</tt>  <tt class="py-line"> </tt>
<a name="Equivalence.update"></a><div id="Equivalence.update-def"><a name="L56"></a><tt class="py-lineno"> 56</tt> <a class="py-toggle" href="#" id="Equivalence.update-toggle" onclick="return toggle('Equivalence.update');">-</a><tt class="py-line">    <tt class="py-keyword">def</tt> <a class="py-def-name" href="equivalence.Equivalence-class.html#update">update</a><tt class="py-op">(</tt><tt class="py-param">self</tt><tt class="py-op">,</tt> <tt class="py-op">*</tt><tt class="py-param">objects</tt><tt class="py-op">)</tt><tt class="py-op">:</tt> </tt>
</div><div id="Equivalence.update-collapsed" style="display:none;" pad="+++" indent="++++++++"></div><div id="Equivalence.update-expanded"><a name="L57"></a><tt class="py-lineno"> 57</tt>  <tt class="py-line">        <tt class="py-docstring">'''Update this equivalence with the given objects.'''</tt> </tt>
<a name="L58"></a><tt class="py-lineno"> 58</tt>  <tt class="py-line">        <tt class="py-name">join</tt><tt class="py-op">,</tt><tt class="py-name">rank</tt><tt class="py-op">,</tt><tt class="py-name">child2parent</tt> <tt class="py-op">=</tt> <tt class="py-name">self</tt><tt class="py-op">.</tt><tt id="link-4" class="py-name" targets="Method equivalence.BidirectionalEquivalence._join()=equivalence.BidirectionalEquivalence-class.html#_join,Method equivalence.Equivalence._join()=equivalence.Equivalence-class.html#_join"><a title="equivalence.BidirectionalEquivalence._join
equivalence.Equivalence._join" class="py-name" href="#" onclick="return doclink('link-4', '_join', 'link-4');">_join</a></tt><tt class="py-op">,</tt><tt class="py-name">self</tt><tt class="py-op">.</tt><tt class="py-name">_rank</tt><tt class="py-op">,</tt><tt class="py-name">self</tt><tt class="py-op">.</tt><tt class="py-name">_child2parent</tt> </tt>
<a name="L59"></a><tt class="py-lineno"> 59</tt>  <tt class="py-line">        <tt class="py-keyword">for</tt> <tt class="py-name">obj</tt> <tt class="py-keyword">in</tt> <tt class="py-name">objects</tt><tt class="py-op">:</tt> </tt>
<a name="L60"></a><tt class="py-lineno"> 60</tt>  <tt class="py-line">            <tt class="py-keyword">if</tt> <tt class="py-name">obj</tt> <tt class="py-keyword">not</tt> <tt class="py-keyword">in</tt> <tt class="py-name">child2parent</tt><tt class="py-op">:</tt> </tt>
<a name="L61"></a><tt class="py-lineno"> 61</tt>  <tt class="py-line">                <tt class="py-name">join</tt><tt class="py-op">(</tt><tt class="py-name">obj</tt><tt class="py-op">)</tt> </tt>
<a name="L62"></a><tt class="py-lineno"> 62</tt>  <tt class="py-line">                <tt class="py-name">rank</tt><tt class="py-op">[</tt><tt class="py-name">obj</tt><tt class="py-op">]</tt> <tt class="py-op">=</tt> <tt class="py-number">0</tt> </tt>
</div><a name="L63"></a><tt class="py-lineno"> 63</tt>  <tt class="py-line"> </tt>
<a name="Equivalence.merge"></a><div id="Equivalence.merge-def"><a name="L64"></a><tt class="py-lineno"> 64</tt> <a class="py-toggle" href="#" id="Equivalence.merge-toggle" onclick="return toggle('Equivalence.merge');">-</a><tt class="py-line">    <tt class="py-keyword">def</tt> <a class="py-def-name" href="equivalence.Equivalence-class.html#merge">merge</a><tt class="py-op">(</tt><tt class="py-param">self</tt><tt class="py-op">,</tt> <tt class="py-op">*</tt><tt class="py-param">objects</tt><tt class="py-op">)</tt><tt class="py-op">:</tt> </tt>
</div><div id="Equivalence.merge-collapsed" style="display:none;" pad="+++" indent="++++++++"></div><div id="Equivalence.merge-expanded"><a name="L65"></a><tt class="py-lineno"> 65</tt>  <tt class="py-line">        <tt class="py-docstring">'''Merge all the given objects into the same equivalence set.'''</tt> </tt>
<a name="L66"></a><tt class="py-lineno"> 66</tt>  <tt class="py-line">        <tt class="py-keyword">if</tt> <tt class="py-keyword">not</tt> <tt class="py-name">objects</tt><tt class="py-op">:</tt> <tt class="py-keyword">return</tt> </tt>
<a name="L67"></a><tt class="py-lineno"> 67</tt>  <tt class="py-line">        <tt class="py-name">join</tt><tt class="py-op">,</tt><tt class="py-name">rank</tt><tt class="py-op">,</tt><tt class="py-name">find</tt> <tt class="py-op">=</tt> <tt class="py-name">self</tt><tt class="py-op">.</tt><tt id="link-5" class="py-name"><a title="equivalence.BidirectionalEquivalence._join
equivalence.Equivalence._join" class="py-name" href="#" onclick="return doclink('link-5', '_join', 'link-4');">_join</a></tt><tt class="py-op">,</tt><tt class="py-name">self</tt><tt class="py-op">.</tt><tt class="py-name">_rank</tt><tt class="py-op">,</tt><tt class="py-name">self</tt><tt class="py-op">.</tt><tt id="link-6" class="py-name" targets="Method equivalence.Equivalence._find()=equivalence.Equivalence-class.html#_find,Method equivalence.KeyEquivalence._find()=equivalence.KeyEquivalence-class.html#_find"><a title="equivalence.Equivalence._find
equivalence.KeyEquivalence._find" class="py-name" href="#" onclick="return doclink('link-6', '_find', 'link-6');">_find</a></tt> </tt>
<a name="L68"></a><tt class="py-lineno"> 68</tt>  <tt class="py-line">        <tt class="py-name">objects</tt> <tt class="py-op">=</tt> <tt class="py-name">iter</tt><tt class="py-op">(</tt><tt class="py-name">objects</tt><tt class="py-op">)</tt> </tt>
<a name="L69"></a><tt class="py-lineno"> 69</tt>  <tt class="py-line">        <tt class="py-name">root</tt> <tt class="py-op">=</tt> <tt class="py-name">find</tt><tt class="py-op">(</tt><tt class="py-name">objects</tt><tt class="py-op">.</tt><tt class="py-name">next</tt><tt class="py-op">(</tt><tt class="py-op">)</tt><tt class="py-op">,</tt> <tt class="py-name">True</tt><tt class="py-op">)</tt> </tt>
<a name="L70"></a><tt class="py-lineno"> 70</tt>  <tt class="py-line">        <tt class="py-keyword">for</tt> <tt class="py-name">obj</tt> <tt class="py-keyword">in</tt> <tt class="py-name">objects</tt><tt class="py-op">:</tt> </tt>
<a name="L71"></a><tt class="py-lineno"> 71</tt>  <tt class="py-line">            <tt class="py-name">root2</tt> <tt class="py-op">=</tt> <tt class="py-name">find</tt><tt class="py-op">(</tt><tt class="py-name">obj</tt><tt class="py-op">,</tt><tt class="py-name">True</tt><tt class="py-op">)</tt> </tt>
<a name="L72"></a><tt class="py-lineno"> 72</tt>  <tt class="py-line">            <tt class="py-comment"># union-by-rank</tt> </tt>
<a name="L73"></a><tt class="py-lineno"> 73</tt>  <tt class="py-line"><tt class="py-comment"></tt>            <tt class="py-name">cmp_rank</tt> <tt class="py-op">=</tt> <tt class="py-name">cmp</tt><tt class="py-op">(</tt><tt class="py-name">rank</tt><tt class="py-op">[</tt><tt class="py-name">root</tt><tt class="py-op">]</tt><tt class="py-op">,</tt> <tt class="py-name">rank</tt><tt class="py-op">[</tt><tt class="py-name">root2</tt><tt class="py-op">]</tt><tt class="py-op">)</tt> </tt>
<a name="L74"></a><tt class="py-lineno"> 74</tt>  <tt class="py-line">            <tt class="py-keyword">if</tt> <tt class="py-name">cmp_rank</tt> <tt class="py-op">&gt;</tt> <tt class="py-number">0</tt><tt class="py-op">:</tt> </tt>
<a name="L75"></a><tt class="py-lineno"> 75</tt>  <tt class="py-line">                <tt class="py-name">join</tt><tt class="py-op">(</tt><tt class="py-name">root2</tt><tt class="py-op">,</tt><tt class="py-name">root</tt><tt class="py-op">)</tt> </tt>
<a name="L76"></a><tt class="py-lineno"> 76</tt>  <tt class="py-line">            <tt class="py-keyword">elif</tt> <tt class="py-name">cmp_rank</tt> <tt class="py-op">&lt;</tt> <tt class="py-number">0</tt><tt class="py-op">:</tt> </tt>
<a name="L77"></a><tt class="py-lineno"> 77</tt>  <tt class="py-line">                <tt class="py-name">join</tt><tt class="py-op">(</tt><tt class="py-name">root</tt><tt class="py-op">,</tt><tt class="py-name">root2</tt><tt class="py-op">)</tt> </tt>
<a name="L78"></a><tt class="py-lineno"> 78</tt>  <tt class="py-line">            <tt class="py-keyword">elif</tt> <tt class="py-name">cmp_rank</tt> <tt class="py-op">==</tt> <tt class="py-number">0</tt> <tt class="py-keyword">and</tt> <tt class="py-name">root</tt> <tt class="py-op">!=</tt> <tt class="py-name">root2</tt><tt class="py-op">:</tt> </tt>
<a name="L79"></a><tt class="py-lineno"> 79</tt>  <tt class="py-line">                <tt class="py-name">rank</tt><tt class="py-op">[</tt><tt class="py-name">root</tt><tt class="py-op">]</tt> <tt class="py-op">+=</tt> <tt class="py-number">1</tt> </tt>
<a name="L80"></a><tt class="py-lineno"> 80</tt>  <tt class="py-line">                <tt class="py-name">join</tt><tt class="py-op">(</tt><tt class="py-name">root2</tt><tt class="py-op">,</tt><tt class="py-name">root</tt><tt class="py-op">)</tt> </tt>
</div><a name="L81"></a><tt class="py-lineno"> 81</tt>  <tt class="py-line"> </tt>
<a name="Equivalence.are_equivalent"></a><div id="Equivalence.are_equivalent-def"><a name="L82"></a><tt class="py-lineno"> 82</tt> <a class="py-toggle" href="#" id="Equivalence.are_equivalent-toggle" onclick="return toggle('Equivalence.are_equivalent');">-</a><tt class="py-line">    <tt class="py-keyword">def</tt> <a class="py-def-name" href="equivalence.Equivalence-class.html#are_equivalent">are_equivalent</a><tt class="py-op">(</tt><tt class="py-param">self</tt><tt class="py-op">,</tt> <tt class="py-op">*</tt><tt class="py-param">objects</tt><tt class="py-op">)</tt><tt class="py-op">:</tt> </tt>
</div><div id="Equivalence.are_equivalent-collapsed" style="display:none;" pad="+++" indent="++++++++"></div><div id="Equivalence.are_equivalent-expanded"><a name="L83"></a><tt class="py-lineno"> 83</tt>  <tt class="py-line">        <tt class="py-docstring">'''Check whether all objects are equivalent.</tt> </tt>
<a name="L84"></a><tt class="py-lineno"> 84</tt>  <tt class="py-line"><tt class="py-docstring"></tt> </tt>
<a name="L85"></a><tt class="py-lineno"> 85</tt>  <tt class="py-line"><tt class="py-docstring">        An object doesn't have to be in the equivalence (through `update` or</tt> </tt>
<a name="L86"></a><tt class="py-lineno"> 86</tt>  <tt class="py-line"><tt class="py-docstring">        `merge`) in order to appear as an argument.</tt> </tt>
<a name="L87"></a><tt class="py-lineno"> 87</tt>  <tt class="py-line"><tt class="py-docstring"></tt> </tt>
<a name="L88"></a><tt class="py-lineno"> 88</tt>  <tt class="py-line"><tt class="py-docstring">        :rtype: bool</tt> </tt>
<a name="L89"></a><tt class="py-lineno"> 89</tt>  <tt class="py-line"><tt class="py-docstring">        '''</tt> </tt>
<a name="L90"></a><tt class="py-lineno"> 90</tt>  <tt class="py-line">        <tt class="py-keyword">if</tt> <tt class="py-keyword">not</tt> <tt class="py-name">objects</tt><tt class="py-op">:</tt> </tt>
<a name="L91"></a><tt class="py-lineno"> 91</tt>  <tt class="py-line">            <tt class="py-keyword">raise</tt> <tt class="py-name">ValueError</tt><tt class="py-op">(</tt><tt class="py-string">'No objects given'</tt><tt class="py-op">)</tt> </tt>
<a name="L92"></a><tt class="py-lineno"> 92</tt>  <tt class="py-line">        <tt class="py-name">find</tt> <tt class="py-op">=</tt> <tt class="py-name">self</tt><tt class="py-op">.</tt><tt id="link-7" class="py-name"><a title="equivalence.Equivalence._find
equivalence.KeyEquivalence._find" class="py-name" href="#" onclick="return doclink('link-7', '_find', 'link-6');">_find</a></tt> </tt>
<a name="L93"></a><tt class="py-lineno"> 93</tt>  <tt class="py-line">        <tt class="py-name">objects</tt> <tt class="py-op">=</tt> <tt class="py-name">iter</tt><tt class="py-op">(</tt><tt class="py-name">objects</tt><tt class="py-op">)</tt> </tt>
<a name="L94"></a><tt class="py-lineno"> 94</tt>  <tt class="py-line">        <tt class="py-name">root</tt> <tt class="py-op">=</tt> <tt class="py-name">find</tt><tt class="py-op">(</tt><tt class="py-name">objects</tt><tt class="py-op">.</tt><tt class="py-name">next</tt><tt class="py-op">(</tt><tt class="py-op">)</tt><tt class="py-op">)</tt> </tt>
<a name="L95"></a><tt class="py-lineno"> 95</tt>  <tt class="py-line">        <tt class="py-keyword">for</tt> <tt class="py-name">obj</tt> <tt class="py-keyword">in</tt> <tt class="py-name">objects</tt><tt class="py-op">:</tt> </tt>
<a name="L96"></a><tt class="py-lineno"> 96</tt>  <tt class="py-line">            <tt class="py-keyword">if</tt> <tt class="py-name">find</tt><tt class="py-op">(</tt><tt class="py-name">obj</tt><tt class="py-op">)</tt> <tt class="py-op">!=</tt> <tt class="py-name">root</tt><tt class="py-op">:</tt> </tt>
<a name="L97"></a><tt class="py-lineno"> 97</tt>  <tt class="py-line">                <tt class="py-keyword">return</tt> <tt class="py-name">False</tt> </tt>
<a name="L98"></a><tt class="py-lineno"> 98</tt>  <tt class="py-line">        <tt class="py-keyword">return</tt> <tt class="py-name">True</tt> </tt>
</div><a name="L99"></a><tt class="py-lineno"> 99</tt>  <tt class="py-line"> </tt>
<a name="Equivalence.partitions"></a><div id="Equivalence.partitions-def"><a name="L100"></a><tt class="py-lineno">100</tt> <a class="py-toggle" href="#" id="Equivalence.partitions-toggle" onclick="return toggle('Equivalence.partitions');">-</a><tt class="py-line">    <tt class="py-keyword">def</tt> <a class="py-def-name" href="equivalence.Equivalence-class.html#partitions">partitions</a><tt class="py-op">(</tt><tt class="py-param">self</tt><tt class="py-op">,</tt> <tt class="py-param">objects</tt><tt class="py-op">=</tt><tt class="py-name">None</tt><tt class="py-op">)</tt><tt class="py-op">:</tt> </tt>
</div><div id="Equivalence.partitions-collapsed" style="display:none;" pad="+++" indent="++++++++"></div><div id="Equivalence.partitions-expanded"><a name="L101"></a><tt class="py-lineno">101</tt>  <tt class="py-line">        <tt class="py-docstring">'''Return the partitioning of `objects` into equivalence groups.</tt> </tt>
<a name="L102"></a><tt class="py-lineno">102</tt>  <tt class="py-line"><tt class="py-docstring"></tt> </tt>
<a name="L103"></a><tt class="py-lineno">103</tt>  <tt class="py-line"><tt class="py-docstring">        :type objects: Iterable or None</tt> </tt>
<a name="L104"></a><tt class="py-lineno">104</tt>  <tt class="py-line"><tt class="py-docstring">        :param objects: If not None, it must be an iterable of objects to be</tt> </tt>
<a name="L105"></a><tt class="py-lineno">105</tt>  <tt class="py-line"><tt class="py-docstring">            partitioned. Otherwise, it defaults to the objects already inserted</tt> </tt>
<a name="L106"></a><tt class="py-lineno">106</tt>  <tt class="py-line"><tt class="py-docstring">            in the equivalence (through `update` and `merge`).</tt> </tt>
<a name="L107"></a><tt class="py-lineno">107</tt>  <tt class="py-line"><tt class="py-docstring">        :rtype: list of lists</tt> </tt>
<a name="L108"></a><tt class="py-lineno">108</tt>  <tt class="py-line"><tt class="py-docstring">        :returns: A list of partitions, each partition being a list of equivalent</tt> </tt>
<a name="L109"></a><tt class="py-lineno">109</tt>  <tt class="py-line"><tt class="py-docstring">            objects. Note that if the passed argument contains duplicates, so</tt> </tt>
<a name="L110"></a><tt class="py-lineno">110</tt>  <tt class="py-line"><tt class="py-docstring">            will the respective partition list, i.e. the partition is not a set.</tt> </tt>
<a name="L111"></a><tt class="py-lineno">111</tt>  <tt class="py-line"><tt class="py-docstring">        '''</tt> </tt>
<a name="L112"></a><tt class="py-lineno">112</tt>  <tt class="py-line">        <tt class="py-name">find</tt> <tt class="py-op">=</tt> <tt class="py-name">self</tt><tt class="py-op">.</tt><tt id="link-8" class="py-name"><a title="equivalence.Equivalence._find
equivalence.KeyEquivalence._find" class="py-name" href="#" onclick="return doclink('link-8', '_find', 'link-6');">_find</a></tt> </tt>
<a name="L113"></a><tt class="py-lineno">113</tt>  <tt class="py-line">        <tt class="py-name">key2partition</tt> <tt class="py-op">=</tt> <tt class="py-name">defaultdict</tt><tt class="py-op">(</tt><tt class="py-name">list</tt><tt class="py-op">)</tt> </tt>
<a name="L114"></a><tt class="py-lineno">114</tt>  <tt class="py-line">        <tt class="py-keyword">if</tt> <tt class="py-name">objects</tt> <tt class="py-keyword">is</tt> <tt class="py-name">None</tt><tt class="py-op">:</tt> </tt>
<a name="L115"></a><tt class="py-lineno">115</tt>  <tt class="py-line">            <tt class="py-name">objects</tt> <tt class="py-op">=</tt> <tt class="py-name">self</tt><tt class="py-op">.</tt><tt id="link-9" class="py-name" targets="Method equivalence.Equivalence._iter_objects()=equivalence.Equivalence-class.html#_iter_objects,Method equivalence.KeyEquivalence._iter_objects()=equivalence.KeyEquivalence-class.html#_iter_objects"><a title="equivalence.Equivalence._iter_objects
equivalence.KeyEquivalence._iter_objects" class="py-name" href="#" onclick="return doclink('link-9', '_iter_objects', 'link-9');">_iter_objects</a></tt><tt class="py-op">(</tt><tt class="py-op">)</tt> </tt>
<a name="L116"></a><tt class="py-lineno">116</tt>  <tt class="py-line">        <tt class="py-keyword">for</tt> <tt class="py-name">obj</tt> <tt class="py-keyword">in</tt> <tt class="py-name">objects</tt><tt class="py-op">:</tt> </tt>
<a name="L117"></a><tt class="py-lineno">117</tt>  <tt class="py-line">            <tt class="py-name">key2partition</tt><tt class="py-op">[</tt><tt class="py-name">find</tt><tt class="py-op">(</tt><tt class="py-name">obj</tt><tt class="py-op">)</tt><tt class="py-op">]</tt><tt class="py-op">.</tt><tt class="py-name">append</tt><tt class="py-op">(</tt><tt class="py-name">obj</tt><tt class="py-op">)</tt> </tt>
<a name="L118"></a><tt class="py-lineno">118</tt>  <tt class="py-line">        <tt class="py-keyword">return</tt> <tt class="py-name">key2partition</tt><tt class="py-op">.</tt><tt class="py-name">values</tt><tt class="py-op">(</tt><tt class="py-op">)</tt> </tt>
</div><a name="L119"></a><tt class="py-lineno">119</tt>  <tt class="py-line"> </tt>
<a name="Equivalence.partition"></a><div id="Equivalence.partition-def"><a name="L120"></a><tt class="py-lineno">120</tt> <a class="py-toggle" href="#" id="Equivalence.partition-toggle" onclick="return toggle('Equivalence.partition');">-</a><tt class="py-line">    <tt class="py-keyword">def</tt> <a class="py-def-name" href="equivalence.Equivalence-class.html#partition">partition</a><tt class="py-op">(</tt><tt class="py-param">self</tt><tt class="py-op">,</tt> <tt class="py-param">obj</tt><tt class="py-op">)</tt><tt class="py-op">:</tt> </tt>
</div><div id="Equivalence.partition-collapsed" style="display:none;" pad="+++" indent="++++++++"></div><div id="Equivalence.partition-expanded"><a name="L121"></a><tt class="py-lineno">121</tt>  <tt class="py-line">        <tt class="py-docstring">'''Return the set of objects in the equivalence that are equivalent to</tt> </tt>
<a name="L122"></a><tt class="py-lineno">122</tt>  <tt class="py-line"><tt class="py-docstring">        `obj`.</tt> </tt>
<a name="L123"></a><tt class="py-lineno">123</tt>  <tt class="py-line"><tt class="py-docstring"></tt> </tt>
<a name="L124"></a><tt class="py-lineno">124</tt>  <tt class="py-line"><tt class="py-docstring">        :attention: This implementation is linear to the number of objects in the</tt> </tt>
<a name="L125"></a><tt class="py-lineno">125</tt>  <tt class="py-line"><tt class="py-docstring">            equivalence. If you call this a lot, you might want to use a</tt> </tt>
<a name="L126"></a><tt class="py-lineno">126</tt>  <tt class="py-line"><tt class="py-docstring">            `BidirectionalEquivalence` instance instead.</tt> </tt>
<a name="L127"></a><tt class="py-lineno">127</tt>  <tt class="py-line"><tt class="py-docstring"></tt> </tt>
<a name="L128"></a><tt class="py-lineno">128</tt>  <tt class="py-line"><tt class="py-docstring">        :rtype: set</tt> </tt>
<a name="L129"></a><tt class="py-lineno">129</tt>  <tt class="py-line"><tt class="py-docstring">        '''</tt> </tt>
<a name="L130"></a><tt class="py-lineno">130</tt>  <tt class="py-line">        <tt class="py-name">find</tt> <tt class="py-op">=</tt> <tt class="py-name">self</tt><tt class="py-op">.</tt><tt id="link-10" class="py-name"><a title="equivalence.Equivalence._find
equivalence.KeyEquivalence._find" class="py-name" href="#" onclick="return doclink('link-10', '_find', 'link-6');">_find</a></tt> </tt>
<a name="L131"></a><tt class="py-lineno">131</tt>  <tt class="py-line">        <tt class="py-name">root</tt> <tt class="py-op">=</tt> <tt class="py-name">find</tt><tt class="py-op">(</tt><tt class="py-name">obj</tt><tt class="py-op">)</tt> </tt>
<a name="L132"></a><tt class="py-lineno">132</tt>  <tt class="py-line">        <tt class="py-keyword">return</tt> <tt class="py-name">set</tt><tt class="py-op">(</tt><tt class="py-name">obj</tt> <tt class="py-keyword">for</tt> <tt class="py-name">obj</tt> <tt class="py-keyword">in</tt> <tt class="py-name">self</tt><tt class="py-op">.</tt><tt class="py-name">_child2parent</tt> <tt class="py-keyword">if</tt> <tt class="py-name">find</tt><tt class="py-op">(</tt><tt class="py-name">obj</tt><tt class="py-op">)</tt> <tt class="py-op">==</tt> <tt class="py-name">root</tt><tt class="py-op">)</tt> </tt>
</div><a name="L133"></a><tt class="py-lineno">133</tt>  <tt class="py-line"> </tt>
<a name="L134"></a><tt class="py-lineno">134</tt>  <tt class="py-line">    <tt class="py-comment">#--------- 'protected' methods ---------------------------------------------</tt> </tt>
<a name="L135"></a><tt class="py-lineno">135</tt>  <tt class="py-line"><tt class="py-comment"></tt> </tt>
<a name="Equivalence._find"></a><div id="Equivalence._find-def"><a name="L136"></a><tt class="py-lineno">136</tt> <a class="py-toggle" href="#" id="Equivalence._find-toggle" onclick="return toggle('Equivalence._find');">-</a><tt class="py-line">    <tt class="py-keyword">def</tt> <a class="py-def-name" href="equivalence.Equivalence-class.html#_find">_find</a><tt class="py-op">(</tt><tt class="py-param">self</tt><tt class="py-op">,</tt> <tt class="py-param">obj</tt><tt class="py-op">,</tt> <tt class="py-param">insert_if_missing</tt><tt class="py-op">=</tt><tt class="py-name">False</tt><tt class="py-op">)</tt><tt class="py-op">:</tt> </tt>
</div><div id="Equivalence._find-collapsed" style="display:none;" pad="+++" indent="++++++++"></div><div id="Equivalence._find-expanded"><a name="L137"></a><tt class="py-lineno">137</tt>  <tt class="py-line">        <tt class="py-docstring">'''The 'find' part of the union-find algorithm.</tt> </tt>
<a name="L138"></a><tt class="py-lineno">138</tt>  <tt class="py-line"><tt class="py-docstring"></tt> </tt>
<a name="L139"></a><tt class="py-lineno">139</tt>  <tt class="py-line"><tt class="py-docstring">        :param obj: The object whose tree root is to be returned.</tt> </tt>
<a name="L140"></a><tt class="py-lineno">140</tt>  <tt class="py-line"><tt class="py-docstring">        :type insert_if_missing: bool</tt> </tt>
<a name="L141"></a><tt class="py-lineno">141</tt>  <tt class="py-line"><tt class="py-docstring">        :param insert_if_missing: If true and `obj` is not already in this</tt> </tt>
<a name="L142"></a><tt class="py-lineno">142</tt>  <tt class="py-line"><tt class="py-docstring">            equivalence, add it as a new singleton tree.</tt> </tt>
<a name="L143"></a><tt class="py-lineno">143</tt>  <tt class="py-line"><tt class="py-docstring">        :returns: The root of `obj`'s tree.</tt> </tt>
<a name="L144"></a><tt class="py-lineno">144</tt>  <tt class="py-line"><tt class="py-docstring">        '''</tt> </tt>
<a name="L145"></a><tt class="py-lineno">145</tt>  <tt class="py-line">        <tt class="py-keyword">if</tt> <tt class="py-name">obj</tt> <tt class="py-keyword">not</tt> <tt class="py-keyword">in</tt> <tt class="py-name">self</tt><tt class="py-op">.</tt><tt class="py-name">_child2parent</tt><tt class="py-op">:</tt> </tt>
<a name="L146"></a><tt class="py-lineno">146</tt>  <tt class="py-line">            <tt class="py-keyword">if</tt> <tt class="py-name">insert_if_missing</tt><tt class="py-op">:</tt> </tt>
<a name="L147"></a><tt class="py-lineno">147</tt>  <tt class="py-line">                <tt class="py-name">self</tt><tt class="py-op">.</tt><tt id="link-11" class="py-name"><a title="equivalence.BidirectionalEquivalence._join
equivalence.Equivalence._join" class="py-name" href="#" onclick="return doclink('link-11', '_join', 'link-4');">_join</a></tt><tt class="py-op">(</tt><tt class="py-name">obj</tt><tt class="py-op">)</tt> </tt>
<a name="L148"></a><tt class="py-lineno">148</tt>  <tt class="py-line">                <tt class="py-name">self</tt><tt class="py-op">.</tt><tt class="py-name">_rank</tt><tt class="py-op">[</tt><tt class="py-name">obj</tt><tt class="py-op">]</tt> <tt class="py-op">=</tt> <tt class="py-number">0</tt> </tt>
<a name="L149"></a><tt class="py-lineno">149</tt>  <tt class="py-line">        <tt class="py-keyword">else</tt><tt class="py-op">:</tt> </tt>
<a name="L150"></a><tt class="py-lineno">150</tt>  <tt class="py-line">            <tt class="py-name">parent</tt> <tt class="py-op">=</tt> <tt class="py-name">self</tt><tt class="py-op">.</tt><tt class="py-name">_child2parent</tt><tt class="py-op">[</tt><tt class="py-name">obj</tt><tt class="py-op">]</tt> </tt>
<a name="L151"></a><tt class="py-lineno">151</tt>  <tt class="py-line">            <tt class="py-keyword">if</tt> <tt class="py-name">parent</tt> <tt class="py-keyword">is</tt> <tt class="py-keyword">not</tt> <tt class="py-name">None</tt><tt class="py-op">:</tt> </tt>
<a name="L152"></a><tt class="py-lineno">152</tt>  <tt class="py-line">                <tt class="py-name">root</tt> <tt class="py-op">=</tt> <tt class="py-name">self</tt><tt class="py-op">.</tt><tt id="link-12" class="py-name"><a title="equivalence.Equivalence._find
equivalence.KeyEquivalence._find" class="py-name" href="#" onclick="return doclink('link-12', '_find', 'link-6');">_find</a></tt><tt class="py-op">(</tt><tt class="py-name">parent</tt><tt class="py-op">)</tt> </tt>
<a name="L153"></a><tt class="py-lineno">153</tt>  <tt class="py-line">                <tt class="py-name">self</tt><tt class="py-op">.</tt><tt id="link-13" class="py-name"><a title="equivalence.BidirectionalEquivalence._join
equivalence.Equivalence._join" class="py-name" href="#" onclick="return doclink('link-13', '_join', 'link-4');">_join</a></tt><tt class="py-op">(</tt><tt class="py-name">obj</tt><tt class="py-op">,</tt> <tt class="py-name">root</tt><tt class="py-op">)</tt>   <tt class="py-comment"># path compression</tt> </tt>
<a name="L154"></a><tt class="py-lineno">154</tt>  <tt class="py-line">                <tt class="py-name">obj</tt> <tt class="py-op">=</tt> <tt class="py-name">root</tt> </tt>
<a name="L155"></a><tt class="py-lineno">155</tt>  <tt class="py-line">        <tt class="py-keyword">return</tt> <tt class="py-name">obj</tt> </tt>
</div><a name="L156"></a><tt class="py-lineno">156</tt>  <tt class="py-line"> </tt>
<a name="Equivalence._join"></a><div id="Equivalence._join-def"><a name="L157"></a><tt class="py-lineno">157</tt> <a class="py-toggle" href="#" id="Equivalence._join-toggle" onclick="return toggle('Equivalence._join');">-</a><tt class="py-line">    <tt class="py-keyword">def</tt> <a class="py-def-name" href="equivalence.Equivalence-class.html#_join">_join</a><tt class="py-op">(</tt><tt class="py-param">self</tt><tt class="py-op">,</tt> <tt class="py-param">obj</tt><tt class="py-op">,</tt> <tt class="py-param">parent</tt><tt class="py-op">=</tt><tt class="py-name">None</tt><tt class="py-op">)</tt><tt class="py-op">:</tt> </tt>
</div><div id="Equivalence._join-collapsed" style="display:none;" pad="+++" indent="++++++++"></div><div id="Equivalence._join-expanded"><a name="L158"></a><tt class="py-lineno">158</tt>  <tt class="py-line">        <tt class="py-docstring">'''Join `obj` to its parent (or None if it's the root).'''</tt> </tt>
<a name="L159"></a><tt class="py-lineno">159</tt>  <tt class="py-line">        <tt class="py-name">self</tt><tt class="py-op">.</tt><tt class="py-name">_child2parent</tt><tt class="py-op">[</tt><tt class="py-name">obj</tt><tt class="py-op">]</tt> <tt class="py-op">=</tt> <tt class="py-name">parent</tt> </tt>
</div><a name="L160"></a><tt class="py-lineno">160</tt>  <tt class="py-line"> </tt>
<a name="Equivalence._iter_objects"></a><div id="Equivalence._iter_objects-def"><a name="L161"></a><tt class="py-lineno">161</tt> <a class="py-toggle" href="#" id="Equivalence._iter_objects-toggle" onclick="return toggle('Equivalence._iter_objects');">-</a><tt class="py-line">    <tt class="py-keyword">def</tt> <a class="py-def-name" href="equivalence.Equivalence-class.html#_iter_objects">_iter_objects</a><tt class="py-op">(</tt><tt class="py-param">self</tt><tt class="py-op">)</tt><tt class="py-op">:</tt> </tt>
</div><div id="Equivalence._iter_objects-collapsed" style="display:none;" pad="+++" indent="++++++++"></div><div id="Equivalence._iter_objects-expanded"><a name="L162"></a><tt class="py-lineno">162</tt>  <tt class="py-line">        <tt class="py-docstring">'''Return an iterator over all the objects of the equivalence.'''</tt> </tt>
<a name="L163"></a><tt class="py-lineno">163</tt>  <tt class="py-line">        <tt class="py-keyword">return</tt> <tt class="py-name">self</tt><tt class="py-op">.</tt><tt class="py-name">_child2parent</tt><tt class="py-op">.</tt><tt class="py-name">iterkeys</tt><tt class="py-op">(</tt><tt class="py-op">)</tt> </tt>
</div></div><a name="L164"></a><tt class="py-lineno">164</tt>  <tt class="py-line"> </tt>
<a name="L165"></a><tt class="py-lineno">165</tt>  <tt class="py-line"> </tt>
<a name="BidirectionalEquivalence"></a><div id="BidirectionalEquivalence-def"><a name="L166"></a><tt class="py-lineno">166</tt> <a class="py-toggle" href="#" id="BidirectionalEquivalence-toggle" onclick="return toggle('BidirectionalEquivalence');">-</a><tt class="py-line"><tt class="py-keyword">class</tt> <a class="py-def-name" href="equivalence.BidirectionalEquivalence-class.html">BidirectionalEquivalence</a><tt class="py-op">(</tt><tt class="py-base-class">Equivalence</tt><tt class="py-op">)</tt><tt class="py-op">:</tt> </tt>
</div><div id="BidirectionalEquivalence-collapsed" style="display:none;" pad="+++" indent="++++"></div><div id="BidirectionalEquivalence-expanded"><a name="L167"></a><tt class="py-lineno">167</tt>  <tt class="py-line">    <tt class="py-docstring">'''Equivalence with fast `partition` method.</tt> </tt>
<a name="L168"></a><tt class="py-lineno">168</tt>  <tt class="py-line"><tt class="py-docstring"></tt> </tt>
<a name="L169"></a><tt class="py-lineno">169</tt>  <tt class="py-line"><tt class="py-docstring">    This class implements a `partition` method that takes linear time to the size</tt> </tt>
<a name="L170"></a><tt class="py-lineno">170</tt>  <tt class="py-line"><tt class="py-docstring">    of the respective partition, as opposed to the size of the whole equivalence.</tt> </tt>
<a name="L171"></a><tt class="py-lineno">171</tt>  <tt class="py-line"><tt class="py-docstring">    The downside is increased memory overhead and extra constant factor cost for</tt> </tt>
<a name="L172"></a><tt class="py-lineno">172</tt>  <tt class="py-line"><tt class="py-docstring">    the rest methods.</tt> </tt>
<a name="L173"></a><tt class="py-lineno">173</tt>  <tt class="py-line"><tt class="py-docstring">    '''</tt> </tt>
<a name="L174"></a><tt class="py-lineno">174</tt>  <tt class="py-line"> </tt>
<a name="BidirectionalEquivalence.__init__"></a><div id="BidirectionalEquivalence.__init__-def"><a name="L175"></a><tt class="py-lineno">175</tt> <a class="py-toggle" href="#" id="BidirectionalEquivalence.__init__-toggle" onclick="return toggle('BidirectionalEquivalence.__init__');">-</a><tt class="py-line">    <tt class="py-keyword">def</tt> <a class="py-def-name" href="equivalence.BidirectionalEquivalence-class.html#__init__">__init__</a><tt class="py-op">(</tt><tt class="py-param">self</tt><tt class="py-op">)</tt><tt class="py-op">:</tt> </tt>
</div><div id="BidirectionalEquivalence.__init__-collapsed" style="display:none;" pad="+++" indent="++++++++"></div><div id="BidirectionalEquivalence.__init__-expanded"><a name="L176"></a><tt class="py-lineno">176</tt>  <tt class="py-line">        <tt class="py-name">super</tt><tt class="py-op">(</tt><tt id="link-14" class="py-name"><a title="equivalence.BidirectionalEquivalence" class="py-name" href="#" onclick="return doclink('link-14', 'BidirectionalEquivalence', 'link-0');">BidirectionalEquivalence</a></tt><tt class="py-op">,</tt><tt class="py-name">self</tt><tt class="py-op">)</tt><tt class="py-op">.</tt><tt id="link-15" class="py-name" targets="Method equivalence.BidirectionalEquivalence.__init__()=equivalence.BidirectionalEquivalence-class.html#__init__,Method equivalence.Equivalence.__init__()=equivalence.Equivalence-class.html#__init__,Method equivalence.KeyEquivalence.__init__()=equivalence.KeyEquivalence-class.html#__init__"><a title="equivalence.BidirectionalEquivalence.__init__
equivalence.Equivalence.__init__
equivalence.KeyEquivalence.__init__" class="py-name" href="#" onclick="return doclink('link-15', '__init__', 'link-15');">__init__</a></tt><tt class="py-op">(</tt><tt class="py-op">)</tt> </tt>
<a name="L177"></a><tt class="py-lineno">177</tt>  <tt class="py-line">        <tt class="py-comment"># inverted mapping of self._child2parent</tt> </tt>
<a name="L178"></a><tt class="py-lineno">178</tt>  <tt class="py-line"><tt class="py-comment"></tt>        <tt class="py-name">self</tt><tt class="py-op">.</tt><tt class="py-name">_parent2children</tt> <tt class="py-op">=</tt> <tt class="py-name">defaultdict</tt><tt class="py-op">(</tt><tt class="py-name">set</tt><tt class="py-op">)</tt> </tt>
</div><a name="L179"></a><tt class="py-lineno">179</tt>  <tt class="py-line"> </tt>
<a name="BidirectionalEquivalence.partition"></a><div id="BidirectionalEquivalence.partition-def"><a name="L180"></a><tt class="py-lineno">180</tt> <a class="py-toggle" href="#" id="BidirectionalEquivalence.partition-toggle" onclick="return toggle('BidirectionalEquivalence.partition');">-</a><tt class="py-line">    <tt class="py-keyword">def</tt> <a class="py-def-name" href="equivalence.BidirectionalEquivalence-class.html#partition">partition</a><tt class="py-op">(</tt><tt class="py-param">self</tt><tt class="py-op">,</tt> <tt class="py-param">obj</tt><tt class="py-op">)</tt><tt class="py-op">:</tt> </tt>
</div><div id="BidirectionalEquivalence.partition-collapsed" style="display:none;" pad="+++" indent="++++++++"></div><div id="BidirectionalEquivalence.partition-expanded"><a name="L181"></a><tt class="py-lineno">181</tt>  <tt class="py-line">        <tt class="py-docstring">'''Return the set of objects in the equivalence that are equivalent to</tt> </tt>
<a name="L182"></a><tt class="py-lineno">182</tt>  <tt class="py-line"><tt class="py-docstring">        `obj`.</tt> </tt>
<a name="L183"></a><tt class="py-lineno">183</tt>  <tt class="py-line"><tt class="py-docstring"></tt> </tt>
<a name="L184"></a><tt class="py-lineno">184</tt>  <tt class="py-line"><tt class="py-docstring">        :rtype: set</tt> </tt>
<a name="L185"></a><tt class="py-lineno">185</tt>  <tt class="py-line"><tt class="py-docstring">        '''</tt> </tt>
<a name="L186"></a><tt class="py-lineno">186</tt>  <tt class="py-line">        <tt class="py-name">p</tt> <tt class="py-op">=</tt> <tt class="py-name">set</tt><tt class="py-op">(</tt><tt class="py-op">)</tt> </tt>
<a name="L187"></a><tt class="py-lineno">187</tt>  <tt class="py-line">        <tt class="py-keyword">if</tt> <tt class="py-name">obj</tt> <tt class="py-keyword">in</tt> <tt class="py-name">self</tt><tt class="py-op">.</tt><tt class="py-name">_child2parent</tt><tt class="py-op">:</tt> </tt>
<a name="L188"></a><tt class="py-lineno">188</tt>  <tt class="py-line">            <tt class="py-keyword">def</tt> <tt class="py-def-name">recurse</tt><tt class="py-op">(</tt><tt class="py-param">node</tt><tt class="py-op">,</tt> <tt class="py-param">get_children</tt><tt class="py-op">=</tt><tt class="py-name">self</tt><tt class="py-op">.</tt><tt class="py-name">_parent2children</tt><tt class="py-op">.</tt><tt class="py-name">get</tt><tt class="py-op">,</tt> <tt class="py-param">add</tt><tt class="py-op">=</tt><tt class="py-name">p</tt><tt class="py-op">.</tt><tt class="py-name">add</tt><tt class="py-op">)</tt><tt class="py-op">:</tt> </tt>
<a name="L189"></a><tt class="py-lineno">189</tt>  <tt class="py-line">                <tt class="py-name">add</tt><tt class="py-op">(</tt><tt class="py-name">node</tt><tt class="py-op">)</tt> </tt>
<a name="L190"></a><tt class="py-lineno">190</tt>  <tt class="py-line">                <tt class="py-keyword">for</tt> <tt class="py-name">child</tt> <tt class="py-keyword">in</tt> <tt class="py-name">get_children</tt><tt class="py-op">(</tt><tt class="py-name">node</tt><tt class="py-op">,</tt> <tt class="py-op">(</tt><tt class="py-op">)</tt><tt class="py-op">)</tt><tt class="py-op">:</tt> </tt>
<a name="L191"></a><tt class="py-lineno">191</tt>  <tt class="py-line">                    <tt class="py-name">recurse</tt><tt class="py-op">(</tt><tt class="py-name">child</tt><tt class="py-op">)</tt> </tt>
</div><a name="L192"></a><tt class="py-lineno">192</tt>  <tt class="py-line">            <tt class="py-name">recurse</tt><tt class="py-op">(</tt><tt class="py-name">self</tt><tt class="py-op">.</tt><tt id="link-16" class="py-name"><a title="equivalence.Equivalence._find
equivalence.KeyEquivalence._find" class="py-name" href="#" onclick="return doclink('link-16', '_find', 'link-6');">_find</a></tt><tt class="py-op">(</tt><tt class="py-name">obj</tt><tt class="py-op">)</tt><tt class="py-op">)</tt> </tt>
<a name="L193"></a><tt class="py-lineno">193</tt>  <tt class="py-line">        <tt class="py-keyword">return</tt> <tt class="py-name">p</tt> </tt>
</div><a name="L194"></a><tt class="py-lineno">194</tt>  <tt class="py-line"> </tt>
<a name="BidirectionalEquivalence._join"></a><div id="BidirectionalEquivalence._join-def"><a name="L195"></a><tt class="py-lineno">195</tt> <a class="py-toggle" href="#" id="BidirectionalEquivalence._join-toggle" onclick="return toggle('BidirectionalEquivalence._join');">-</a><tt class="py-line">    <tt class="py-keyword">def</tt> <a class="py-def-name" href="equivalence.BidirectionalEquivalence-class.html#_join">_join</a><tt class="py-op">(</tt><tt class="py-param">self</tt><tt class="py-op">,</tt> <tt class="py-param">obj</tt><tt class="py-op">,</tt> <tt class="py-param">parent</tt><tt class="py-op">=</tt><tt class="py-name">None</tt><tt class="py-op">)</tt><tt class="py-op">:</tt> </tt>
</div><div id="BidirectionalEquivalence._join-collapsed" style="display:none;" pad="+++" indent="++++++++"></div><div id="BidirectionalEquivalence._join-expanded"><a name="L196"></a><tt class="py-lineno">196</tt>  <tt class="py-line">        <tt class="py-name">super</tt><tt class="py-op">(</tt><tt id="link-17" class="py-name"><a title="equivalence.BidirectionalEquivalence" class="py-name" href="#" onclick="return doclink('link-17', 'BidirectionalEquivalence', 'link-0');">BidirectionalEquivalence</a></tt><tt class="py-op">,</tt><tt class="py-name">self</tt><tt class="py-op">)</tt><tt class="py-op">.</tt><tt id="link-18" class="py-name"><a title="equivalence.BidirectionalEquivalence._join
equivalence.Equivalence._join" class="py-name" href="#" onclick="return doclink('link-18', '_join', 'link-4');">_join</a></tt><tt class="py-op">(</tt><tt class="py-name">obj</tt><tt class="py-op">,</tt> <tt class="py-name">parent</tt><tt class="py-op">)</tt> </tt>
<a name="L197"></a><tt class="py-lineno">197</tt>  <tt class="py-line">        <tt class="py-keyword">if</tt> <tt class="py-name">parent</tt> <tt class="py-keyword">is</tt> <tt class="py-keyword">not</tt> <tt class="py-name">None</tt><tt class="py-op">:</tt> </tt>
<a name="L198"></a><tt class="py-lineno">198</tt>  <tt class="py-line">            <tt class="py-name">self</tt><tt class="py-op">.</tt><tt class="py-name">_parent2children</tt><tt class="py-op">[</tt><tt class="py-name">parent</tt><tt class="py-op">]</tt><tt class="py-op">.</tt><tt class="py-name">add</tt><tt class="py-op">(</tt><tt class="py-name">obj</tt><tt class="py-op">)</tt> </tt>
</div></div><a name="L199"></a><tt class="py-lineno">199</tt>  <tt class="py-line"> </tt>
<a name="L200"></a><tt class="py-lineno">200</tt>  <tt class="py-line"> </tt>
<a name="KeyEquivalence"></a><div id="KeyEquivalence-def"><a name="L201"></a><tt class="py-lineno">201</tt> <a class="py-toggle" href="#" id="KeyEquivalence-toggle" onclick="return toggle('KeyEquivalence');">-</a><tt class="py-line"><tt class="py-keyword">class</tt> <a class="py-def-name" href="equivalence.KeyEquivalence-class.html">KeyEquivalence</a><tt class="py-op">(</tt><tt class="py-base-class">Equivalence</tt><tt class="py-op">)</tt><tt class="py-op">:</tt> </tt>
</div><div id="KeyEquivalence-collapsed" style="display:none;" pad="+++" indent="++++"></div><div id="KeyEquivalence-expanded"><a name="L202"></a><tt class="py-lineno">202</tt>  <tt class="py-line">    <tt class="py-docstring">'''Class that maintains object equivalence with respect to a key function.</tt> </tt>
<a name="L203"></a><tt class="py-lineno">203</tt>  <tt class="py-line"><tt class="py-docstring"></tt> </tt>
<a name="L204"></a><tt class="py-lineno">204</tt>  <tt class="py-line"><tt class="py-docstring">    Given a function ``key(x)``, two objects ``a`` and ``b`` are considered</tt> </tt>
<a name="L205"></a><tt class="py-lineno">205</tt>  <tt class="py-line"><tt class="py-docstring">    equivalent if ``key(a) == key(b)``. Of course, since this class is an</tt> </tt>
<a name="L206"></a><tt class="py-lineno">206</tt>  <tt class="py-line"><tt class="py-docstring">    `Equivalence`, ``a`` and ``b`` are also equivalent after `merge(a,b)`, even</tt> </tt>
<a name="L207"></a><tt class="py-lineno">207</tt>  <tt class="py-line"><tt class="py-docstring">    if their keys are different.</tt> </tt>
<a name="L208"></a><tt class="py-lineno">208</tt>  <tt class="py-line"><tt class="py-docstring">    '''</tt> </tt>
<a name="L209"></a><tt class="py-lineno">209</tt>  <tt class="py-line"> </tt>
<a name="KeyEquivalence.__init__"></a><div id="KeyEquivalence.__init__-def"><a name="L210"></a><tt class="py-lineno">210</tt> <a class="py-toggle" href="#" id="KeyEquivalence.__init__-toggle" onclick="return toggle('KeyEquivalence.__init__');">-</a><tt class="py-line">    <tt class="py-keyword">def</tt> <a class="py-def-name" href="equivalence.KeyEquivalence-class.html#__init__">__init__</a><tt class="py-op">(</tt><tt class="py-param">self</tt><tt class="py-op">,</tt> <tt class="py-param">key</tt><tt class="py-op">)</tt><tt class="py-op">:</tt> </tt>
</div><div id="KeyEquivalence.__init__-collapsed" style="display:none;" pad="+++" indent="++++++++"></div><div id="KeyEquivalence.__init__-expanded"><a name="L211"></a><tt class="py-lineno">211</tt>  <tt class="py-line">        <tt class="py-docstring">'''Initialize this equivalence.</tt> </tt>
<a name="L212"></a><tt class="py-lineno">212</tt>  <tt class="py-line"><tt class="py-docstring"></tt> </tt>
<a name="L213"></a><tt class="py-lineno">213</tt>  <tt class="py-line"><tt class="py-docstring">        :param key: A callable to be used for determining key equivalence. To</tt> </tt>
<a name="L214"></a><tt class="py-lineno">214</tt>  <tt class="py-line"><tt class="py-docstring">            ensure that the equivalence properties are preserved, ``key(x)``</tt> </tt>
<a name="L215"></a><tt class="py-lineno">215</tt>  <tt class="py-line"><tt class="py-docstring">            should remain fixed for a given object ``x``, i.e. it should be</tt> </tt>
<a name="L216"></a><tt class="py-lineno">216</tt>  <tt class="py-line"><tt class="py-docstring">            deterministic and not depend on any mutable state of ``x``.</tt> </tt>
<a name="L217"></a><tt class="py-lineno">217</tt>  <tt class="py-line"><tt class="py-docstring">        '''</tt> </tt>
<a name="L218"></a><tt class="py-lineno">218</tt>  <tt class="py-line">        <tt class="py-name">super</tt><tt class="py-op">(</tt><tt id="link-19" class="py-name"><a title="equivalence.KeyEquivalence" class="py-name" href="#" onclick="return doclink('link-19', 'KeyEquivalence', 'link-3');">KeyEquivalence</a></tt><tt class="py-op">,</tt><tt class="py-name">self</tt><tt class="py-op">)</tt><tt class="py-op">.</tt><tt id="link-20" class="py-name"><a title="equivalence.BidirectionalEquivalence.__init__
equivalence.Equivalence.__init__
equivalence.KeyEquivalence.__init__" class="py-name" href="#" onclick="return doclink('link-20', '__init__', 'link-15');">__init__</a></tt><tt class="py-op">(</tt><tt class="py-op">)</tt> </tt>
<a name="L219"></a><tt class="py-lineno">219</tt>  <tt class="py-line">        <tt class="py-name">self</tt><tt class="py-op">.</tt><tt class="py-name">_keyfunc</tt> <tt class="py-op">=</tt> <tt class="py-name">key</tt> </tt>
<a name="L220"></a><tt class="py-lineno">220</tt>  <tt class="py-line">        <tt class="py-comment"># map each key to the set of objects in the equivalence with this key</tt> </tt>
<a name="L221"></a><tt class="py-lineno">221</tt>  <tt class="py-line"><tt class="py-comment"></tt>        <tt class="py-name">self</tt><tt class="py-op">.</tt><tt class="py-name">_key2objects</tt> <tt class="py-op">=</tt> <tt class="py-name">defaultdict</tt><tt class="py-op">(</tt><tt class="py-name">set</tt><tt class="py-op">)</tt> </tt>
</div><a name="L222"></a><tt class="py-lineno">222</tt>  <tt class="py-line"> </tt>
<a name="KeyEquivalence.update"></a><div id="KeyEquivalence.update-def"><a name="L223"></a><tt class="py-lineno">223</tt> <a class="py-toggle" href="#" id="KeyEquivalence.update-toggle" onclick="return toggle('KeyEquivalence.update');">-</a><tt class="py-line">    <tt class="py-keyword">def</tt> <a class="py-def-name" href="equivalence.KeyEquivalence-class.html#update">update</a><tt class="py-op">(</tt><tt class="py-param">self</tt><tt class="py-op">,</tt> <tt class="py-op">*</tt><tt class="py-param">objects</tt><tt class="py-op">)</tt><tt class="py-op">:</tt> </tt>
</div><div id="KeyEquivalence.update-collapsed" style="display:none;" pad="+++" indent="++++++++"></div><div id="KeyEquivalence.update-expanded"><a name="L224"></a><tt class="py-lineno">224</tt>  <tt class="py-line">        <tt class="py-name">keys</tt> <tt class="py-op">=</tt> <tt class="py-name">self</tt><tt class="py-op">.</tt><tt id="link-21" class="py-name" targets="Method equivalence.KeyEquivalence._update_key2objects()=equivalence.KeyEquivalence-class.html#_update_key2objects"><a title="equivalence.KeyEquivalence._update_key2objects" class="py-name" href="#" onclick="return doclink('link-21', '_update_key2objects', 'link-21');">_update_key2objects</a></tt><tt class="py-op">(</tt><tt class="py-name">objects</tt><tt class="py-op">)</tt> </tt>
<a name="L225"></a><tt class="py-lineno">225</tt>  <tt class="py-line">        <tt class="py-name">super</tt><tt class="py-op">(</tt><tt id="link-22" class="py-name"><a title="equivalence.KeyEquivalence" class="py-name" href="#" onclick="return doclink('link-22', 'KeyEquivalence', 'link-3');">KeyEquivalence</a></tt><tt class="py-op">,</tt><tt class="py-name">self</tt><tt class="py-op">)</tt><tt class="py-op">.</tt><tt id="link-23" class="py-name" targets="Method equivalence.Equivalence.update()=equivalence.Equivalence-class.html#update,Method equivalence.KeyEquivalence.update()=equivalence.KeyEquivalence-class.html#update"><a title="equivalence.Equivalence.update
equivalence.KeyEquivalence.update" class="py-name" href="#" onclick="return doclink('link-23', 'update', 'link-23');">update</a></tt><tt class="py-op">(</tt><tt class="py-op">*</tt><tt class="py-name">keys</tt><tt class="py-op">)</tt> </tt>
</div><a name="L226"></a><tt class="py-lineno">226</tt>  <tt class="py-line"> </tt>
<a name="KeyEquivalence.merge"></a><div id="KeyEquivalence.merge-def"><a name="L227"></a><tt class="py-lineno">227</tt> <a class="py-toggle" href="#" id="KeyEquivalence.merge-toggle" onclick="return toggle('KeyEquivalence.merge');">-</a><tt class="py-line">    <tt class="py-keyword">def</tt> <a class="py-def-name" href="equivalence.KeyEquivalence-class.html#merge">merge</a><tt class="py-op">(</tt><tt class="py-param">self</tt><tt class="py-op">,</tt> <tt class="py-op">*</tt><tt class="py-param">objects</tt><tt class="py-op">)</tt><tt class="py-op">:</tt> </tt>
</div><div id="KeyEquivalence.merge-collapsed" style="display:none;" pad="+++" indent="++++++++"></div><div id="KeyEquivalence.merge-expanded"><a name="L228"></a><tt class="py-lineno">228</tt>  <tt class="py-line">        <tt class="py-name">self</tt><tt class="py-op">.</tt><tt id="link-24" class="py-name"><a title="equivalence.KeyEquivalence._update_key2objects" class="py-name" href="#" onclick="return doclink('link-24', '_update_key2objects', 'link-21');">_update_key2objects</a></tt><tt class="py-op">(</tt><tt class="py-name">objects</tt><tt class="py-op">)</tt> </tt>
<a name="L229"></a><tt class="py-lineno">229</tt>  <tt class="py-line">        <tt class="py-name">super</tt><tt class="py-op">(</tt><tt id="link-25" class="py-name"><a title="equivalence.KeyEquivalence" class="py-name" href="#" onclick="return doclink('link-25', 'KeyEquivalence', 'link-3');">KeyEquivalence</a></tt><tt class="py-op">,</tt> <tt class="py-name">self</tt><tt class="py-op">)</tt><tt class="py-op">.</tt><tt id="link-26" class="py-name" targets="Method equivalence.Equivalence.merge()=equivalence.Equivalence-class.html#merge,Method equivalence.KeyEquivalence.merge()=equivalence.KeyEquivalence-class.html#merge"><a title="equivalence.Equivalence.merge
equivalence.KeyEquivalence.merge" class="py-name" href="#" onclick="return doclink('link-26', 'merge', 'link-26');">merge</a></tt><tt class="py-op">(</tt><tt class="py-op">*</tt><tt class="py-name">objects</tt><tt class="py-op">)</tt> </tt>
</div><a name="L230"></a><tt class="py-lineno">230</tt>  <tt class="py-line"> </tt>
<a name="KeyEquivalence.partition"></a><div id="KeyEquivalence.partition-def"><a name="L231"></a><tt class="py-lineno">231</tt> <a class="py-toggle" href="#" id="KeyEquivalence.partition-toggle" onclick="return toggle('KeyEquivalence.partition');">-</a><tt class="py-line">    <tt class="py-keyword">def</tt> <a class="py-def-name" href="equivalence.KeyEquivalence-class.html#partition">partition</a><tt class="py-op">(</tt><tt class="py-param">self</tt><tt class="py-op">,</tt> <tt class="py-param">obj</tt><tt class="py-op">)</tt><tt class="py-op">:</tt> </tt>
</div><div id="KeyEquivalence.partition-collapsed" style="display:none;" pad="+++" indent="++++++++"></div><div id="KeyEquivalence.partition-expanded"><a name="L232"></a><tt class="py-lineno">232</tt>  <tt class="py-line">        <tt class="py-name">p</tt> <tt class="py-op">=</tt> <tt class="py-name">set</tt><tt class="py-op">(</tt><tt class="py-op">)</tt><tt class="py-op">;</tt> <tt id="link-27" class="py-name"><a title="equivalence.Equivalence.update
equivalence.KeyEquivalence.update" class="py-name" href="#" onclick="return doclink('link-27', 'update', 'link-23');">update</a></tt> <tt class="py-op">=</tt> <tt class="py-name">p</tt><tt class="py-op">.</tt><tt id="link-28" class="py-name"><a title="equivalence.Equivalence.update
equivalence.KeyEquivalence.update" class="py-name" href="#" onclick="return doclink('link-28', 'update', 'link-23');">update</a></tt> </tt>
<a name="L233"></a><tt class="py-lineno">233</tt>  <tt class="py-line">        <tt class="py-name">get_objects</tt> <tt class="py-op">=</tt> <tt class="py-name">self</tt><tt class="py-op">.</tt><tt class="py-name">_key2objects</tt><tt class="py-op">.</tt><tt class="py-name">get</tt> </tt>
<a name="L234"></a><tt class="py-lineno">234</tt>  <tt class="py-line">        <tt class="py-keyword">for</tt> <tt class="py-name">key</tt> <tt class="py-keyword">in</tt> <tt class="py-name">super</tt><tt class="py-op">(</tt><tt id="link-29" class="py-name"><a title="equivalence.KeyEquivalence" class="py-name" href="#" onclick="return doclink('link-29', 'KeyEquivalence', 'link-3');">KeyEquivalence</a></tt><tt class="py-op">,</tt><tt class="py-name">self</tt><tt class="py-op">)</tt><tt class="py-op">.</tt><tt id="link-30" class="py-name" targets="Method equivalence.BidirectionalEquivalence.partition()=equivalence.BidirectionalEquivalence-class.html#partition,Method equivalence.Equivalence.partition()=equivalence.Equivalence-class.html#partition,Method equivalence.KeyEquivalence.partition()=equivalence.KeyEquivalence-class.html#partition"><a title="equivalence.BidirectionalEquivalence.partition
equivalence.Equivalence.partition
equivalence.KeyEquivalence.partition" class="py-name" href="#" onclick="return doclink('link-30', 'partition', 'link-30');">partition</a></tt><tt class="py-op">(</tt><tt class="py-name">self</tt><tt class="py-op">.</tt><tt class="py-name">_keyfunc</tt><tt class="py-op">(</tt><tt class="py-name">obj</tt><tt class="py-op">)</tt><tt class="py-op">)</tt><tt class="py-op">:</tt> </tt>
<a name="L235"></a><tt class="py-lineno">235</tt>  <tt class="py-line">            <tt id="link-31" class="py-name"><a title="equivalence.Equivalence.update
equivalence.KeyEquivalence.update" class="py-name" href="#" onclick="return doclink('link-31', 'update', 'link-23');">update</a></tt><tt class="py-op">(</tt><tt class="py-name">get_objects</tt><tt class="py-op">(</tt><tt class="py-name">key</tt><tt class="py-op">,</tt><tt class="py-op">(</tt><tt class="py-op">)</tt><tt class="py-op">)</tt><tt class="py-op">)</tt> </tt>
<a name="L236"></a><tt class="py-lineno">236</tt>  <tt class="py-line">        <tt class="py-keyword">return</tt> <tt class="py-name">p</tt> </tt>
</div><a name="L237"></a><tt class="py-lineno">237</tt>  <tt class="py-line"> </tt>
<a name="L238"></a><tt class="py-lineno">238</tt>  <tt class="py-line">    <tt class="py-comment">#--------- 'protected' methods ---------------------------------------------</tt> </tt>
<a name="L239"></a><tt class="py-lineno">239</tt>  <tt class="py-line"><tt class="py-comment"></tt> </tt>
<a name="KeyEquivalence._find"></a><div id="KeyEquivalence._find-def"><a name="L240"></a><tt class="py-lineno">240</tt> <a class="py-toggle" href="#" id="KeyEquivalence._find-toggle" onclick="return toggle('KeyEquivalence._find');">-</a><tt class="py-line">    <tt class="py-keyword">def</tt> <a class="py-def-name" href="equivalence.KeyEquivalence-class.html#_find">_find</a><tt class="py-op">(</tt><tt class="py-param">self</tt><tt class="py-op">,</tt> <tt class="py-param">obj</tt><tt class="py-op">,</tt> <tt class="py-param">insert_if_missing</tt><tt class="py-op">=</tt><tt class="py-name">False</tt><tt class="py-op">)</tt><tt class="py-op">:</tt> </tt>
</div><div id="KeyEquivalence._find-collapsed" style="display:none;" pad="+++" indent="++++++++"></div><div id="KeyEquivalence._find-expanded"><a name="L241"></a><tt class="py-lineno">241</tt>  <tt class="py-line">        <tt class="py-keyword">return</tt> <tt class="py-name">super</tt><tt class="py-op">(</tt><tt id="link-32" class="py-name"><a title="equivalence.KeyEquivalence" class="py-name" href="#" onclick="return doclink('link-32', 'KeyEquivalence', 'link-3');">KeyEquivalence</a></tt><tt class="py-op">,</tt><tt class="py-name">self</tt><tt class="py-op">)</tt><tt class="py-op">.</tt><tt id="link-33" class="py-name"><a title="equivalence.Equivalence._find
equivalence.KeyEquivalence._find" class="py-name" href="#" onclick="return doclink('link-33', '_find', 'link-6');">_find</a></tt><tt class="py-op">(</tt><tt class="py-name">self</tt><tt class="py-op">.</tt><tt class="py-name">_keyfunc</tt><tt class="py-op">(</tt><tt class="py-name">obj</tt><tt class="py-op">)</tt><tt class="py-op">,</tt> <tt class="py-name">insert_if_missing</tt><tt class="py-op">)</tt> </tt>
</div><a name="L242"></a><tt class="py-lineno">242</tt>  <tt class="py-line"> </tt>
<a name="KeyEquivalence._iter_objects"></a><div id="KeyEquivalence._iter_objects-def"><a name="L243"></a><tt class="py-lineno">243</tt> <a class="py-toggle" href="#" id="KeyEquivalence._iter_objects-toggle" onclick="return toggle('KeyEquivalence._iter_objects');">-</a><tt class="py-line">    <tt class="py-keyword">def</tt> <a class="py-def-name" href="equivalence.KeyEquivalence-class.html#_iter_objects">_iter_objects</a><tt class="py-op">(</tt><tt class="py-param">self</tt><tt class="py-op">)</tt><tt class="py-op">:</tt> </tt>
</div><div id="KeyEquivalence._iter_objects-collapsed" style="display:none;" pad="+++" indent="++++++++"></div><div id="KeyEquivalence._iter_objects-expanded"><a name="L244"></a><tt class="py-lineno">244</tt>  <tt class="py-line">        <tt class="py-keyword">return</tt> <tt class="py-op">(</tt><tt class="py-name">o</tt> <tt class="py-keyword">for</tt> <tt class="py-name">objects</tt> <tt class="py-keyword">in</tt> <tt class="py-name">self</tt><tt class="py-op">.</tt><tt class="py-name">_key2objects</tt><tt class="py-op">.</tt><tt class="py-name">itervalues</tt><tt class="py-op">(</tt><tt class="py-op">)</tt> <tt class="py-keyword">for</tt> <tt class="py-name">o</tt> <tt class="py-keyword">in</tt> <tt class="py-name">objects</tt><tt class="py-op">)</tt> </tt>
</div><a name="L245"></a><tt class="py-lineno">245</tt>  <tt class="py-line"> </tt>
<a name="KeyEquivalence._update_key2objects"></a><div id="KeyEquivalence._update_key2objects-def"><a name="L246"></a><tt class="py-lineno">246</tt> <a class="py-toggle" href="#" id="KeyEquivalence._update_key2objects-toggle" onclick="return toggle('KeyEquivalence._update_key2objects');">-</a><tt class="py-line">    <tt class="py-keyword">def</tt> <a class="py-def-name" href="equivalence.KeyEquivalence-class.html#_update_key2objects">_update_key2objects</a><tt class="py-op">(</tt><tt class="py-param">self</tt><tt class="py-op">,</tt> <tt class="py-param">objects</tt><tt class="py-op">)</tt><tt class="py-op">:</tt> </tt>
</div><div id="KeyEquivalence._update_key2objects-collapsed" style="display:none;" pad="+++" indent="++++++++"></div><div id="KeyEquivalence._update_key2objects-expanded"><a name="L247"></a><tt class="py-lineno">247</tt>  <tt class="py-line">        <tt class="py-docstring">'''Update the _key2objects data structure.</tt> </tt>
<a name="L248"></a><tt class="py-lineno">248</tt>  <tt class="py-line"><tt class="py-docstring"></tt> </tt>
<a name="L249"></a><tt class="py-lineno">249</tt>  <tt class="py-line"><tt class="py-docstring">        :returns: The keys of the passed objects.</tt> </tt>
<a name="L250"></a><tt class="py-lineno">250</tt>  <tt class="py-line"><tt class="py-docstring">        '''</tt> </tt>
<a name="L251"></a><tt class="py-lineno">251</tt>  <tt class="py-line">        <tt class="py-name">key2objects</tt> <tt class="py-op">=</tt> <tt class="py-name">self</tt><tt class="py-op">.</tt><tt class="py-name">_key2objects</tt> </tt>
<a name="L252"></a><tt class="py-lineno">252</tt>  <tt class="py-line">        <tt class="py-name">keys</tt> <tt class="py-op">=</tt> <tt class="py-name">map</tt><tt class="py-op">(</tt><tt class="py-name">self</tt><tt class="py-op">.</tt><tt class="py-name">_keyfunc</tt><tt class="py-op">,</tt> <tt class="py-name">objects</tt><tt class="py-op">)</tt> </tt>
<a name="L253"></a><tt class="py-lineno">253</tt>  <tt class="py-line">        <tt class="py-keyword">for</tt> <tt class="py-name">key</tt><tt class="py-op">,</tt><tt class="py-name">obj</tt> <tt class="py-keyword">in</tt> <tt class="py-name">izip</tt><tt class="py-op">(</tt><tt class="py-name">keys</tt><tt class="py-op">,</tt> <tt class="py-name">objects</tt><tt class="py-op">)</tt><tt class="py-op">:</tt> </tt>
<a name="L254"></a><tt class="py-lineno">254</tt>  <tt class="py-line">            <tt class="py-name">key2objects</tt><tt class="py-op">[</tt><tt class="py-name">key</tt><tt class="py-op">]</tt><tt class="py-op">.</tt><tt class="py-name">add</tt><tt class="py-op">(</tt><tt class="py-name">obj</tt><tt class="py-op">)</tt> </tt>
<a name="L255"></a><tt class="py-lineno">255</tt>  <tt class="py-line">        <tt class="py-keyword">return</tt> <tt class="py-name">keys</tt> </tt>
</div></div><a name="L256"></a><tt class="py-lineno">256</tt>  <tt class="py-line"> </tt>
<a name="L257"></a><tt class="py-lineno">257</tt>  <tt class="py-line"> </tt>
<a name="KeyBidirectionalEquivalence"></a><div id="KeyBidirectionalEquivalence-def"><a name="L258"></a><tt class="py-lineno">258</tt> <a class="py-toggle" href="#" id="KeyBidirectionalEquivalence-toggle" onclick="return toggle('KeyBidirectionalEquivalence');">-</a><tt class="py-line"><tt class="py-keyword">class</tt> <a class="py-def-name" href="equivalence.KeyBidirectionalEquivalence-class.html">KeyBidirectionalEquivalence</a><tt class="py-op">(</tt><tt class="py-base-class">KeyEquivalence</tt><tt class="py-op">,</tt><tt class="py-base-class">BidirectionalEquivalence</tt><tt class="py-op">)</tt><tt class="py-op">:</tt> </tt>
</div><div id="KeyBidirectionalEquivalence-collapsed" style="display:none;" pad="+++" indent="++++"></div><div id="KeyBidirectionalEquivalence-expanded"><a name="L259"></a><tt class="py-lineno">259</tt>  <tt class="py-line">    <tt class="py-docstring">'''A `KeyEquivalence` that is also `BidirectionalEquivalence`.'''</tt> </tt>
</div><a name="L260"></a><tt class="py-lineno">260</tt>  <tt class="py-line"> </tt><script type="text/javascript">
<!--
expandto(location.href);
// -->
</script>
</pre>
<br />
<!-- ==================== NAVIGATION BAR ==================== -->
<table class="navbar" border="0" width="100%" cellpadding="0"
       bgcolor="#a0c0ff" cellspacing="0">
  <tr valign="middle">
  <!-- Home link -->
      <th bgcolor="#70b0f0" class="navbar-select"
          >&nbsp;&nbsp;&nbsp;Home&nbsp;&nbsp;&nbsp;</th>

  <!-- Tree link -->
      <th>&nbsp;&nbsp;&nbsp;<a
        href="module-tree.html">Trees</a>&nbsp;&nbsp;&nbsp;</th>

  <!-- Index link -->
      <th>&nbsp;&nbsp;&nbsp;<a
        href="identifier-index.html">Indices</a>&nbsp;&nbsp;&nbsp;</th>

  <!-- Help link -->
      <th>&nbsp;&nbsp;&nbsp;<a
        href="help.html">Help</a>&nbsp;&nbsp;&nbsp;</th>

  <!-- Project homepage -->
      <th class="navbar" align="right" width="100%">
        <table border="0" cellpadding="0" cellspacing="0">
          <tr><th class="navbar" align="center"
            >equivalence</th>
          </tr></table></th>
  </tr>
</table>
<table border="0" cellpadding="0" cellspacing="0" width="100%%">
  <tr>
    <td align="left" class="footer">
    Generated by Epydoc 3.0beta1 on Tue Jun 03 17:28:11 2008
    </td>
    <td align="right" class="footer">
      <a href="http://epydoc.sourceforge.net">http://epydoc.sourceforge.net</a>
    </td>
  </tr>
</table>

<script type="text/javascript">
  <!--
  // Private objects are initially displayed (because if
  // javascript is turned off then we want them to be
  // visible); but by default, we want to hide them.  So hide
  // them unless we have a cookie that says to show them.
  checkCookie()
  // -->
</script>
  
</body>
</html>
